第四章 运输问题

1.沃格尔法求初始解
每一行每一列算出两个最小 c_ij 的差作为罚数，选取罚数最大的行或列，选 c_ij 最小的行或者列。
2.位势法检验是否最优
填上数字的格为基变量，检验数为 0。价格 c_ij 等于行位势 + 列位势，同时令第一行位势 u_1=0，即可求出所有位势。求出空格的检验数σ_ij=c_ij-u_i-v_j，有空格检验数小于零即不是最优解，有空格检验数为 0 则无穷多解
3.闭回路法改进得到最优解
选检验数为负数且绝对值最大的空格进行调整。
从这个点开始，为 1 号，画出一条闭回路，找出偶数顶点最小值θ，奇数顶点加上θ，偶数顶点减去θ，保证空格数量不变。

退化问题：
1。初始可行解确定时，同时划去行和列
解决 ：行或列的某个空格填上 0，代表数字格，选择行列中具有最小运价的空格。
2。闭回路调整时，偶数顶点多于一个变成空格
对其中某一个数字格标上 0。

对于标零的格子，如果出现在偶数顶点上，θ取 0。

特殊情况
1。极大化问题
令 c_ij=max(c_ij)－c_ij，原问题变为极小化
2。产销不平衡
增加产地或销地，运价等于 0，总量等于差值。